// 解法1：  hash法，用排序后的字符串作为hash表的key，把异位词作为hash表的值
// 时间复杂度：O(nk \log k)O(nklogk)，其中 nn 是 \textit{strs}strs 中的字符串的数量，kk 是 \textit{strs}strs 中的字符串的的最大长度。需要遍历 nn 个字符串，对于每个字符串，需要 O(k \log k)O(klogk) 的时间进行排序以及 O(1)O(1) 的时间更新哈希表，因此总时间复杂度是 O(nk \log k)O(nklogk)。
// 空间复杂度：O(nk)O(nk)，其中 nn 是 \textit{strs}strs 中的字符串的数量，kk 是 \textit{strs}strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

function groupAnagrams(strs) {
    if(!strs || strs.length===0){
        return [];
    }
    if(strs.length===1){
        return [strs];
    }
    // 用一个map来存储hash数据
    const map = new Map();
    for(let string of strs){
        // 对对每个字符串进行排序，排序结果相同的字符串，则是异位词
        let array = Array.from(string);
        array.sort();
        let key = array.toString();
        // 判断一个排序后的string是否有它的异位词，如果有，就获取异位词数组，如果没有就生成一个数组
        let list = map.get(key)? map.get(key): new Array;
        // 将将当前字符串放入，异位词数组中
        list.push(string)
        // 重新设置当前这组异位词的数组
        map.set(key,list)
    }
    // 返回hash表中，所有的数据
    return Array.from(map.values())
}

// 解法2：计数法，因为互为异位词的两个字符串他们的字符是相同的。
// 因此，因此我们可以遍历一个字符串，统计每个字符出现的次数，将其作为同一组异位词的hash表的key，
// 由于这里每个字符串的字符只能是小写的26个字母，因此我们将用一个26长的数组来记录每个字母出现的次数

function groupAnagrams2(strs) {
    if(!strs || strs.length===0){
        return [];
    }
    if(strs.length===1){
        return [strs];
    }
    const countMap = new Map()
    for(let string of strs){
        // 因为，这里的字符只能是26个小写字母
        // 因此，用一个26长的数组来记录每个字符串他的字母出现的次数，默认每个字符出现的次数是0
        // 并且，以a为基准
        const count = new Array(26).fill(0)
        // 遍历字符串，得到该字符串的字母出现次数的表
        for(let char of string){
            count[char.charCodeAt() - 'a'.charCodeAt()]++;
        }
        
        // 以字符串出现次数，作为异位词的key，一组异位词有同样的key
        let countString = count.toString()
        if(countMap.get(countString)){
            countMap.get(countString).push(string)
        }else{
            countMap.set(countString, [string])
        }
         
    }
    return Array.from(countMap.values())
}


console.log(groupAnagrams2(["eat","tea","tan","ate","nat","bat"]))